package top100;

import java.util.LinkedHashMap;

/**
 * @author Godc
 * @description
 */
public class ReorderList {
    public static void main(String[] args) {
//        ReorderListSolution s = new ReorderListSolution();
//        ListNode root = new ListNode(1);
//        ListNode node1 = new ListNode(2);
//        ListNode node2 = new ListNode(3);
//        ListNode nodee = new ListNode(4);
//        root.next = node1;
//        node1.next = node2;
//        node2.next = nodee;
//        s.reorderList(root);
//        while(root!=null){
//            System.out.println(root.val);
//            root = root.next;
//        }
        SSolution s = new SSolution();
        s.merge(new int[]{},0,new int[]{1},1);
    }
}
class ReorderListSolution {
    public void reorderList(ListNode head) {
        ListNode slow = head,fast = head;
        while(fast.next!=null&&fast.next.next!=null){
            slow = slow.next;
            fast = fast.next.next;
        }
        ListNode mid = slow.next;
        slow.next = null;
        fast = reverse(mid);
        slow = head;
        while(slow!=null&&fast!=null){
            ListNode temp1 = slow.next;
            ListNode temp2 = fast.next;
            slow.next = fast;
            slow = temp1;
            fast.next = slow;
            fast = temp2;
        }
    }
    public ListNode reverse(ListNode head){
        if(head==null||head.next==null) return head;
        ListNode cur = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return cur;

    }
}
class SSolution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if(m==0) {
            nums1 = nums2;
            return;
        }
        if(n==0) return;
        int i = 0,j = 0;
        int[] res = new int[m+n];
        int x = 0;
        while(i<m&&j<n){
            if(nums1[i]<nums2[j]) res[x++] = nums1[i++];
            else res[x++] = nums2[j++];
        }
        while(i<m) res[x++] = nums1[i++];
        while(j<m) res[x++] = nums2[j++];
        for(x = 0;x<m+n;x++){
            nums1[x] = res[x];
        }
    }
}